In the past two decades, many secure transactions have been devised that compute quantities from certain hidden data without revealing all such data. For instance, Yao (in the Proceedings of Foundations of Computer Science Conference, 1982) presented a solution to the so-called Two-Millionaire problem that involved this approach. In this problem, two millionaires wish to know who is richer without revealing their respective monetary worth. In Yao's solution, the parties engage in cryptographic exchange, each encoding in a special manner the amount of money he/she owns. At the end of the exchange, one of the millionaires is in possession of information indicating which of the two is the richer one and can then, without proof, announce the result to the other.
In another example, Goldreich, Micali, and Widgerson presented the first of a series of cryptographic protocols for secure multi-party computation. This protocol enabled n parties (whose majority is honest), where party I has a secret input x.sub.i, to evaluate .function. on their private inputs, without revealing these inputs more than absolutely necessary. At the simplest level, the parties compute y=.function.(x.sub.1, . . . ,x.sub.n) without revealing more about the x.sub.i 's that is implicitly revealed by the value y itself. More sophisticated and precise definitions of this protocol were-later described, for instance in the work Micali and Rogaway.
In the past, traditional physical proximity has encouraged sellers and buyers to negotiate in good faith. Physical proximity creates enough circumstantial evidence of an enforceable agreement, and also requires a considerable investment of time and effort on both sides, thus reducing the buyer's temptation of negotiating just for "curiosity" without any serious intentions of buying. Such goals, however, are more difficult to achieve where business transactions are carried out more and more at a distance (e.g., over an electronic network). Consider the example of purchasing a house over the Internet. Photographic information of a piece of property is readily available over the Internet, and digital signatures may help in signing a contract. However, in this new setting, it is possible for a seller to negotiate with many potential buyers simultaneously and at a distance so that the various buyers may not be aware of each other. The seller can then use one buyer's offer for obtaining better offers from others, even with stringent time constraints. At the same time, the new setting makes it very convenient for uncommitted buyers just to shop around for a seller's "true" price, and then possibly sell this information to others.
There remains a need in the art to provide cryptographic protocols that enable parties to negotiate and consummate business and other transactions electronically.